package com.sort;


import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

public class Sort {
    public static void main(String[] args) {
//        int arr[] = {853, 74, 512, 27, 1, 53, 601, 256};
////        int temp[] = new int[arr.length];
//        radixSort(arr);
//        mergerSort(arr,0,arr.length-1,temp);
//        System.out.println(Arrays.toString(arr));
        //测试时间复杂度O(n^2)的冒泡排序性能，对8w个随机数进行排序所用耗时
        int[] arr = new int[80000];
        for (int i = 0 ; i < arr.length;i++){
        //  random()参数[0,1)之间的数
            arr[i] = (int) (Math.random()*200000);
        }
        long strat = System.currentTimeMillis();
        //int[] temp = new int[arr.length];
        //887
        //quickSort(arr,0,arr.length-1);
        //1737
        radixSort(arr);
        long end = System.currentTimeMillis();

        System.out.println("耗时："+(end-strat));

    }

    /**
     * 冒泡排序：相邻元素两两进行比较，一共进行n-1趟，每趟比较n-1-i次
     * 时间复杂度：O(n^2),8w数据测试：8932
     */
    public static void bubbleSort(int[] arr) {
        System.out.println("BubbleSort:");
        int temp = 0;//用于交换的临时遍历
        //外循环一共n-1次
        boolean flag = true;
        for (int i = 0; i < arr.length - 1; i++) {
            //小循环一共n-1-i次，将最大的数字排到后面
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    //只要有一次交换过程，即认为这些数是无序的
                    //一旦所有数都有序后，就不会再进入这个判断内，也就无需再进行下去了,直接break终止循环
                    flag = false;
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
            if (flag) {
                break;
            } else {
                flag = true;
            }
        }
    }

    /**
     * 选择排序：默认第1个为最小值，依次比较2-n的大小，如果有更小的，记录下标后和第1个数进行交换；同理将第2个视为最小，依次和3-n个数比较 ...
     * 时间复杂度：O(n^2),8w数据测试：2085
     *
     * @param arr
     */
    public static void selectSort(int[] arr) {
        int minIndex = 0;
        int min = 0;
        for (int i = 0; i < arr.length - 1; i++) {
            minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                //记录最小值的下标
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            //如果最小下标没有改变，即本身已经是最小的了，则不用交换
            if (minIndex != i) {
                min = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = min;
            }
        }
    }

    /**
     * 插入排序：将第一个元素视为有序序列，后面的元素视为无序序列，将无序序列中每个元素插入到有序序列中正确的位置
     * 时间复杂度：O(n^2),8w数据测试：509
     *
     * @param arr
     */
    public static void insertSort(int[] arr) {
        int insertValue = 0;
        int insertIndex = 0;
        for (int i = 1; i < arr.length; i++) {
            insertValue = arr[i];
            //插入元素前面即为有序列表，从后面依次往前进行比较，找到元素插入的正确的位置
            insertIndex = i - 1;
            while (insertIndex >= 0 && insertValue < arr[insertIndex]) {
                //将比待插入元素大的元素后移
                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex--;
            }
            //循环结束以后的Index即为比待插入元素小的元素的下标，将待插入元素插入到该下标后面即可
            //如果待插入元素已经在正确的位置(即最大),则无需交换
            if (insertIndex + 1 != i) {
                arr[insertIndex + 1] = insertValue;
            }

//            System.out.println("第"+i+"次循环:"+Arrays.toString(arr));
        }
    }

    /**
     * 希尔排序（缩小增量排序）：插入排序的改进版，将待排序的数进行分组，在每个组里进行直接插入排序
     * 时间复杂度：O(nlogn), 8w数据用时：15, 800w:1758
     *
     * @param arr
     */
    public static void shellSort(int[] arr) {
        int temp = 0;// 辅助变量
        /*
        // 希尔排序的第1轮排序
        // 因为第1轮排序，是将10个数据分成了 5组，每组中的元素分别为0,1,2,3,4
        // [3, 5, 1, 6, 0, 8, 9, 4, 7, 2]
        for (int i = 5; i < arr.length; i++) {
            // 将当前元素加入到该组中，遍历该组中所有元素，从后往前进行冒泡排序，将小的元素排到前面
            for (int j = i - 5; j >= 0; j -= 5) {
                // 如果当前元素大于加上步长后的那个元素，说明交换
                if (arr[j] > arr[j + 5]) {
                    temp = arr[j];
                    arr[j] = arr[j + 5];
                    arr[j + 5] = temp;
                }
            }
        }
        System.out.println("第一轮排序：" + Arrays.toString(arr));
        */

        /*
         * 希尔排序交换法（内部排序通过两两比较找到正确的位置），8w数据用时：4846
         */
//        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
//            for (int i = gap; i < arr.length; i++) {
//                for (int j = i - gap; j >= 0; j -= gap) {
//                    if (arr[j] > arr[j + gap]) {
//                        temp = arr[j];
//                        arr[j] = arr[j + gap];
//                        arr[j + gap] = temp;
//                    }
//                }
//            }
//            //  System.out.println(Arrays.toString(arr));
//        }

        /*
         * 希尔排序移位法（内部排序通过直接插入进行排序），8w数据用时：15
         */
        int insertValue;
        int insertIndex;
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                insertValue = arr[i];
                insertIndex = i - gap;
                while (insertIndex >= 0 && insertValue < arr[insertIndex]) {
                    arr[insertIndex + gap] = arr[insertIndex];
                    insertIndex -= gap;
                }
                if (insertIndex + gap != i) {
                    arr[insertIndex + gap] = insertValue;
                }
            }
//            System.out.println(Arrays.toString(arr));
        }
    }

    /**
     * 快速排序：将第一个数作为基数，将数组分为基数左边全比基数小，基数右边全比基数大，再对两边使用快速排序
     * 时间复杂度：O(nlogn), 8w数据用时：20, 800w 887
     *
     * @param arr
     * @param left
     * @param right
     */
    public static void quickSort(int[] arr, int left, int right) {
        //递归的终止条件
        //当递归到最后，每个分组中只有1个数的时候，则排序已完成，终止递归
        if (left > right) {
            return;
        }
        int l = left;
        int r = right;
        int pivot = arr[left];
        int temp;
        while (l < r) {
            while (arr[r] >= pivot && l < r) {
                r--;
            }
            while (arr[l] <= pivot && l < r) {
                l++;
            }

            if (l < r) {
                temp = arr[l];
                arr[l] = arr[r];
                arr[r] = temp;
            }
        }
        arr[left] = arr[l];
        arr[l] = pivot;
        quickSort(arr, left, l - 1);
        quickSort(arr, r + 1, right);
    }

    /**
     * 归并排序，通过递归将排序数组进行分解，再调用合并方法进行合并
     * 缺点：需要开辟临时的空间来存储排序数列。即用空间换时间
     * 时间复杂度：O(nlogn),8W数据测试：11ms
     *
     * @param arr
     */
    public static void mergerSort(int arr[], int left, int right, int[] temp) {
        // 8,4,5,7,1,3,6,2
        //如果left = right,表示分解到只有一个元素了，则递归停止
        if (left < right) {
            int mid = (left + right) / 2;
            mergerSort(arr, left, mid, temp);
            mergerSort(arr, mid + 1, right, temp);
            merger(arr, left, mid, right, temp);
        }

    }

    public static void merger(int arr[], int left, int mid, int right, int[] temp) {
        //左边有序序列的初始索引
        int l = left;
        //右边有序序列的初始索引
        int m = mid + 1;
        //临时数组的初始索引
        int t = 0;

        //1.先将左右两边的有序序列按规则填充到temp中，直到有一边全部处理完成
        while (l <= mid && m <= right) {
            //比较左右两边当前元素的大小，将小的一方加入到temp中，并移动索引指针
            if (arr[l] <= arr[m]) {
                temp[t++] = arr[l++];
            } else {
                temp[t++] = arr[m++];

            }
        }
        //2.当有一边处理完成后，将另一半有序序列中剩余的数加入到temp中
        while (l <= mid) {
            temp[t++] = arr[l++];

        }

        while (m <= right) {
            temp[t++] = arr[m++];
        }

        //3.将temp中的元素拷贝到arr中,并不是每次都拷贝8个元素
        t = 0;
        int tempLeft = left;
        while (tempLeft <= right) {
            arr[tempLeft++] = temp[t++];
        }

    }


    /**
     * 基数排序：从最低位开始，依次按位数放入对应的桶中，再按顺序取出放入原来的数组中
     */
    public static void radixSort(int arr[]) {
        HashMap<Integer, LinkedList<Integer>> bucket = new HashMap<>();
        //对Map进行初始化
        for (int i = 0; i < 10; i++) {
            bucket.put(i, new LinkedList<Integer>());
        }
        //第一轮，针对每个元素的个位进行排序
        //首先要获取数组中最大元素的位数，位数即代表进行多少轮次
        int maxNum = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (maxNum < arr[i])
                maxNum = arr[i];
        }
        //获取最大元素的位数，length()为String中的方法，所以需要将int转换成String来获取长度
        int maxLength = (maxNum + "").length();
        //表示进行的轮数
        for (int j = 0, n = 1; j < maxLength; j++, n *= 10) {
            //将所有元素按照第位数依次放入桶中
            for (int i = 0; i < arr.length; i++) {
                int index = (arr[i] / n) % 10;
                bucket.get(index).add(arr[i]);
            }
            int index = 0;
            //再将桶中的元素重新放回数组中
            for (int i = 0; i < 10; i++) {
                for (Integer num : bucket.get(i)) {
                    arr[index++] = num;
                }
            }
            //重新放回数组以后需要清空桶中的元素
            for (int i = 0; i < 10; i++) {
                bucket.get(i).clear();
            }
        }
//        System.out.println(Arrays.toString(arr));

    }

}
